package com.lihepeng.leecode.array;

/**
 * 我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
 * <p>
 * B.length >= 3
 * 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
 * （注意：B 可以是 A 的任意子数组，包括整个数组 A。）
 * <p>
 * 给出一个整数数组 A，返回最长 “山脉” 的长度。
 * <p>
 * 如果不含有 “山脉” 则返回 0。
 * 示例 1：
 * 输入：[2,1,4,7,3,2,5]
 * 输出：5
 * 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
 * 示例 2：
 * 输入：[2,2,2]
 * 输出：0
 * 解释：不含 “山脉”。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-mountain-in-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution845 {
    // 枚举山脚
    public int longestMountain(int[] A) {
        // 如果长度小于3 构不成山脉 直接返回
        int alength = A.length;
        int ans = 0;
        int left = 0;
        while (left + 2 < alength) {
            int right = left + 1;
            if (A[left] < A[left + 1]) {
                while (right + 1 < alength && A[right] < A[right + 1]) {
                    ++right;
                }
                if (right < alength - 1 && A[right] > A[right + 1]) {
                    while (right + 1 < alength && A[right] > A[right + 1]) {
                        ++right;
                    }
                    ans = Math.max(ans, right - left + 1);
                } else {
                    ++right;
                }
            }
            left = right;
        }

        return ans;
    }

    // 枚举山头元素
    // 使用动态规划完成
    public int longestMountain01(int[] A) {
        int alen = A.length;
        // 元素少于3个构不成山
        if (alen < 3) {
            return 0;
        }
        int[] left = new int[alen];
        // left [i] 表示 左边元素可以向左拓展的个数
        // 当i =0 的时候不能向左拓展，当a[i-1]>=a[i] 的时候不能拓展

        for (int i = 1; i < alen; ++i) {
            left[i] = A[i - 1] < A[i] ? left[i - 1] + 1 : 0;
        }
        int[] right = new int[alen];
        for (int i = 1; i < alen; ++i) {
            right[i] = A[i + 1] < A[i] ? right[i + 1] + 1 : 0;
        }
        int ans = 0;
        for (int i = 0; i < alen; i++) {
            if (left[i] > 0 && right[i] > 0) {
                ans = Math.max(ans, left[i] + right[i] + 1);
            }
        }
        return ans;
    }
}
